/**
 * Project Name:javaBaseReview
 * Package Name:com.xuwei.base.link
 * author:David
 * Date:2015年6月14日下午1:38:26
 * Copyright (c) 2015, xw123box@126.com All Rights Reserved.
 *
 */
package com.xuwei.base.link;

import java.util.ArrayList;
import java.util.List;

/**
 * 单向循环链表
 * @author David
 * @since 2015年6月14日 下午1:38:26
 * @version 
 * @since JDK 1.6
 */
public class CycSingleLink {
	private LNode head;//头指针:用来指向第一个结点，但不是链表第一个结点
	public int length;//链表的长度,即结点数目
	/**
	 * 构建链表
	 * @param n结点数
	 */
	public void createLink(int length){
		head=new LNode();
		LNode rear=head,p;
		for(int i=0;i<length;i++){
			p=new LNode();
			p.setData(i);
			rear.setNext(p);
			rear=p;
			rear.setNext(head.getNext());
		}
		this.length=length;
	}
	
	/**
	 * 打印链表
	 */
	public void printLink(){
		if(head.getNext()==null){
			System.out.println("null");
			return;
		}
		LNode p=head.getNext();
		do{
			System.out.print(p.getData()+"->");
			p=p.getNext();
		}while(p!=head.getNext());
		System.out.println("end");
	}
	
	
	public LNode searchByIndex(int index){
		LNode p=head.getNext();
		if(index<0||index>length-1){
			throw new RuntimeException("The index Out of Boundary of link!");
		}
		for(int i=0;i<index;i++){
			p=p.getNext();
		}
		return p;
	}
	
	
	public List<LNode> searchByVal(int val){
		List<LNode> list=new ArrayList<LNode>();
		LNode p=head.getNext();
		do{
			if(val==p.getData()){
				list.add(p);
			}
			p=p.getNext();
			
		}while(p!=head.getNext());
		return list;
	}
	
	//删除特定结点
	public void remove(LNode node){
		LNode p=head.getNext();
		LNode tail=head.getNext();
		do{
		  tail=tail.getNext();
		}while(tail.getNext()!=head.getNext());//找到链表的最后一个结点
		
		if(node==p){//头结点特殊处理
			head.setNext(p.getNext());
			tail.setNext(p.getNext());
			return;
		}
		LNode q;
		do{
			if(p.getNext()==node){
				q=p.getNext();
				p.setNext(q.getNext());
				break;
			}
			p=p.getNext();
		}while(p!=head.getNext());
	}
	
	public void deleteByIndex(int index){
		//TODO
		
	}
	
	public void deleteByVal(){
		//TODO
	}
	
	//增加结点
	public void add(LNode node){
		insertLast(node);
	}
	
	/**
	 * 从链表头部插入新结点
	 * @param node
	 */
	public void insertFirst(LNode node){
		LNode p=head.getNext();
		node.setNext(p);
		head.setNext(node);
	}
	
	/**
	 * 从链表尾部插入新结点
	 */
	public void insertLast(LNode node){
		LNode p=head.getNext();
		do{
			p=p.getNext();
		}while(p.getNext()!=head.getNext());
		node.setNext(head.getNext());
		p.setNext(node);	
		
	}
	
	/**
	 * 在某结点后插入新结点
	 * @param pos
	 * @param node
	 */
	public void insertAfter(LNode pos,LNode node){
		LNode p=head.getNext();
		do{
			if(p==pos){
				node.setNext(p.getNext());
				p.setNext(node);
				break;
			}
			p=p.getNext();
		}while(p.getNext()!=p);
	}
	
	//清空链表
	public void clear(){
		head.setNext(null);
		this.length=0;
	}
	
	public static void main(String[] args) {
		CycSingleLink link=new CycSingleLink();
		link.createLink(8);
		link.printLink();
		LNode node1=link.searchByIndex(6);
		System.out.println("search res:"+node1.getData());
		
//		List<LNode> node2=link.searchByVal(6);
//		System.out.println("search res:"+node2.get(0).getData());
		
//		link.clear();
//		link.printLink();
		
//		LNode node3=new LNode();
//		node3.setData(23);
//		LNode node4=new LNode();
//		node4.setData(3);
//		link.add(node3);
//		link.add(node4);
//		link.printLink();
//		
//		List<LNode> node5=link.searchByVal(3);
//		for(LNode p:node5){
//			System.out.println("search res:"+p.getData());
//		}
		
//		link.insertFirst(node4);
//		link.printLink();
//		link.clear();
//		link.printLink();
//		
//		LNode node7=new LNode();
//		node7.setData(123);
//		link.insertAfter(node1, node7);
//		link.printLink();
//		node7=new LNode();
//		node7.setData(32);
//		link.insertAfter(node1, node7);
//		link.printLink();
		
//		link.remove(node1);
//		LNode node_0=link.searchByIndex(0);
//		link.remove(node_0);
		LNode node_end=link.searchByIndex(7);
		link.remove(node_end);
		link.printLink();
		
		
	}
}
